import java.util.*;

public class Text {
    /*
    题目1 ： 最佳买卖股票的时机
     */
    //给定一个数组 prices ，它的第i 个元素prices[i] 表示一支给定股票第 i 天的价格。
    //你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
    //返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0
    //考虑个别情况和普遍情况

    public int maxProfit(int[] prices) {
        int min = prices[0];
        int maxprofit = 0;
        for(int i = 1; i < prices.length; i++){
            if(prices[i] < min){
                min = prices[i];
            }else{
                if(prices[i] - min > maxprofit){
                    maxprofit = prices[i] - min;
                }
            }
        }
        return maxprofit;
    }

    public static void main1(String[] args) {
        int[][] mat = {{2,5,6,4},{36,5,7,2}};
        int len = mat[0].length;
        System.out.println(len);
    }

    /*
    题目2 ： 转换矩阵
     */

    public int[][] matrixReshape1(int[][] mat, int r, int c) {
        int row = mat.length;
        int colunm = mat[0].length;
        if(row * colunm != r * c){
            return mat;
        }
        int[][] newmat = new int[r][c];

        int rowindex = 0;
        int colindex = 0;
        for(int i = 0; i < mat.length;i++){
            for(int j = 0; j < mat[0].length;j++){
                if(colindex < c){
                    newmat[rowindex][colindex++] = mat[i][j];
                }else{
                    if(rowindex < r){
                        rowindex++;
                        colindex = 0;
                        newmat[rowindex][colindex++] = mat[i][j];
                    }
                }
            }
        }
        return newmat;
    }

    //官方答案:
    //行和列的理解：把 m * n 个数字分成 m 组，每组里有 n 个数字！
    public int[][] matrixReshape(int[][] mat, int r, int c) {
        int m = mat.length;
        int n = mat[0].length;

        if(m * n != r * c){
            return mat;
        }

        int[][] mat1 = new int[r][c];

        for(int i = 0 ; i < m * n;i++){
            mat1[i / c][i % c] = mat[i / n][i % n];
        }

        return mat1;
    }

    /*
    题目3 : 杨辉三角形
     */
    public List<List<Integer>> generate1(int numRows) {
        List<List<Integer>> list = new LinkedList<>();
        List<Integer> row = new LinkedList<>();
        row.add(1);
        list.add(row);

        for(int i = 1 ; i < numRows ;i++){
            List<Integer> prerow = list.get(i - 1);
            List<Integer> currow = new LinkedList<>();
            currow.add(1);
            for(int j = 1; j < prerow.size(); j++){
                currow.add(prerow.get(j) + prerow.get(j - 1));

            }
            currow.add(1);
            list.add(currow);
        }
        return list;
    }

    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> list = new LinkedList<>();
        List<Integer> row = new LinkedList<>();
        row.add(1);
        list.add(row);
        for (int i = 1; i < numRows; i++) {
            List<Integer> prerow = list.get(i - 1);
            List<Integer> currow = new LinkedList<>();
            currow.add(1);
            for (int j = 1; j < prerow.size(); j++) {
                currow.add(prerow.get(j) + prerow.get(j - 1));
            }
            currow.add(1);
            list.add(currow);
        }
        return list;
    }

    /*
    题目4 ： 计算力扣银行中的钱
     */
    //等差数列
    public int totalMoney(int n) {
        int quotient = n / 7;
        int mod = n % 7;
        int an = 28 + (quotient - 1) * 7;
        int sum = (28 + an) * quotient / 2;
        for(int i = 0;i < mod; i++){
            sum += ++quotient;
        }
        return sum;
    }

    /*
    题目5 ： 删除中间节点
     */
    class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
  }
    public void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }

    /*
    题目 6 ：重新排列的数组
     */
    //交换
    private void swap(int[] nums,int i ,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public int[] shuffle(int[] nums, int n) {
        int i = 1;
        while(n - i >= 1){
            for(int j = n - i + 1; j <= 2 * (n - i);j++){
                swap(nums, j - 1,j);
            }
            i++;
        }
        return nums;
    }

    //杨氏矩阵：矩阵从左到右元素递增，从上到下，元素递增
    //查找的过程本质就是排除的过程，一次排除的个数多，效率就高

}
